#include <stdio.h>
/*
 * 快速排序：
 * 前提：从小从大进行排序  采用数组进行存值
 * 核心思想：
 *  1.选择一个中间值
 *  2.将小于中间值的元素全放到左边
 *  3.将大于中间值的元素全放到右边
 *  4.重复上述过程对左边和右边进行排序
 * */

/*
 * 函数名：quickSort
 * 输入：无序的数组arr,搜索范围左边的指针，右边的指针
 * 输出：无
 * */

int partition(int arr[],int left,int right){
    //进行快速排序
    //1.选取中间值，将第一个值作为中间值
    int mid =arr[left];//mid是中间值元素
    //2.划分 将小于中间值的放左边，大于中间值的放右边
    while(left<right){
        while(left<right&&arr[right]>mid)
            right--;
        arr[left]=arr[right];//当循环结束，在右边找到小于mid的值，将其放到左边
       // while(left<right&&arr[left]<arr[mid])
        while(left<right&&arr[left]<mid)
            left++;
        arr[right]=arr[left];//当循环结束，在左边找到大于mid的值，将其放到右边
    }
    //将中间值放到最终的位置上
    arr[left]=mid;
    return left;
}
void quickSort(int arr[],int left,int right){
    //排序的前提
    if(left<right){
        int pos = partition(arr,left,right);
        //左边递归调用
        quickSort(arr,left,pos-1);
        //右边递归调用
        quickSort(arr,pos+1,right);

    }
}

int main() {
    int arr[5]={4,2,1,6,5};
    quickSort(arr,0,4);
   // printf("Hello, World!\n");
    return 0;
}
